package com.mengfou.linklist;

import java.util.Stack;

/**
 * 判断链表是否为回文链表
 * @author mengfou
 * 2022-1-10 09:47:45
 */
public class PalindromicList {

    /**
     * 回文链表
     * @param list 链表
     * @return 是否为回文链表
     */
    public boolean palindromicList_2(Node list) {
        if (list == null) return true;
        // 可以尝试使用快慢指针来找链表的中点，然后分奇偶进行讨论
        Node fast = list, slow = list;
        boolean isOdd = false;
        while(true){
            if(fast.next != null){
                fast = fast.next.next;
                if(fast == null) break; // 偶数
                if(fast.next == null) { // 奇数
                    isOdd = true;
                    break;
                }
            } else{
                break;
            }
            slow = slow.next;
        }
        if(isOdd) slow = slow.next;
        Node midBefore = slow.next;
        slow.next = null; // 断链
        Node reverseList = reverseList(midBefore);
        // 等值判断
        Node temp = reverseList, qtr = list;
        while(temp != null){
            if(qtr.val != temp.val) return false;
            temp = temp.next;
            qtr = qtr.next;
        }
        // 把链表还原
        slow.next = reverseList(reverseList);
        return true;
    }

    /**
     * 反转链表
     * @param list 链表
     * @return 反转后链表
     */
    private Node reverseList(Node list) {
        Node dummyNode = new Node(-1);
        dummyNode.next = null;
        Node ptr = list, temp = null;
        while(ptr != null){
            temp = ptr.next;
            ptr.next = dummyNode.next;
            dummyNode.next = ptr;
            ptr = temp;
        }
        return dummyNode.next;
    }

    /**
     * 判断链表是否是回文结构（方法一）
     * 直接使用栈来，时间复杂度为O(n)，空间复杂度为O(n)
     * 2022-1-8
     * @param list 链表
     * @return 是否为回文链表
     */
    public boolean palindromicList_1(Node list){
        if(list == null) return true;
        Stack<Integer> stack = new Stack<>();
        Node ptr = list;
        // 数据压入栈中
        while(ptr != null){
            stack.push(ptr.val);
            ptr = ptr.next;
        }
        // 遍历和弹栈同时进行
        ptr = list;
        while(ptr != null){
            if(ptr.val != stack.pop()) return false;
            ptr = ptr.next;
        }
        return true;
    }
}
